#if 0
#include <stdio.h>
#include <stdlib.h>

/*

中序线索二叉树
n个结点的二叉树，有n+1个空链域，可以用来记录前驱，后继的信息

*/
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef struct ThreadNode
{
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag; //左右线索标志
    /*
    tag为1的时候，表示指针是线索
    tag为0的时候，表示指针是孩子
    */
} ThreadNode, *ThreadTree;

//用土方法找中继前驱结点
BiTNode *final, *pre;
void findPre(BiTree T, BiTNode *p) // p是目标结点
{
    if (T != NULL)
    {
        findPre(T->lchild, p);
        if (T->data == p->data)
        {
            final = pre;
            return;
        }
        else
        {
            pre = T;
        }
        findPre(T->rchild, p);
    }
}

//中序线索化
ThreadNode *pre2 = NULL;
void InThread(ThreadTree T)
{
    if (T != NULL)
    {
        InThread(T->lchild);
        if (T->lchild == NULL)
        {
            T->lchild = pre2; //左子树为空建立前驱线索
            T->ltag = 1;
        }
        if (pre2 != NULL && pre->rchild == NULL)
        {
            pre2->rchild = T; //建立前驱结点的后继线索
            pre2->rtag = 1;
        }
        pre2 = T;

        InThread(T->rchild);
    }
}
void createInThread(ThreadTree T)
{
    InThread(T);
    if (pre2->rchild != NULL) //处理最后一个结点
    {
        pre2->rtag = 1;
    }
}

//先序线索化
ThreadNode *pre3 = NULL;
void preThread(ThreadTree T)
{
    if (T != NULL)
    {
        if (T->lchild == NULL)
        {
            T->lchild = pre3; //注意再次之后T的左孩子不为空，所以下一轮如果不加其他考虑那么会在这里无线循环
            T->ltag = 1;
        }
        if (pre3 != NULL && pre3->rchild == NULL)
        {
            pre3->rchild = T;
            pre3->rtag = 1;
        }
        pre3 = T;
        if (T->ltag == 0) //避免死循环
        {
            preThread(T->lchild);
        }
        preThread(T->rchild);
    }
}
void createPreThread(ThreadTree T)
{
    preThread(T);
    if (pre3->rchild == NULL)
    {
        pre3->rtag = 1;
    }
}

//后序线索化
ThreadNode *pre4 = NULL;
void PostThread(ThreadTree T)
{
    if (T != NULL)
    {
        PostThread(T->lchild);
        PostThread(T->rchild);
        if (T->lchild == NULL)
        {
            T->lchild = pre4;
            T->ltag = 1;
        }
        if (pre4 != NULL && pre4->rchild == NULL)
        {
            pre4->rchild = T;
            pre4->rtag = 1;
        }
    }
}
void creatdPostThread(ThreadTree T)
{
    PostThread(T);
    if (pre4->rchild == NULL)
    {
        pre4->rtag = 1;
    }
}

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}
#endif

#if 1
#include <stdio.h>
#include <stdlib.h>

typedef struct ThreadNode
{
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag; //左右线索标志
    /*
    tag为1的时候，表示指针是线索
    tag为0的时候，表示指针是孩子
    */
} ThreadNode, *ThreadTree;

//找指定结点中序后继
/*
如果当前结点的右孩子没有左孩子，那么当前结点的后继结点就是该结点的右孩子
如果当前结点的右孩子有左孩子，那么后继结点就是当前结点右子树中最左下结点

*/
ThreadNode *NextNode(ThreadNode *p)
{
    if (p->rtag == 0)
    {
        ThreadNode *q = p;
        //循环找到最左下结点（不一定是叶子结点）
        while (q->ltag == 0 && q->lchild != NULL)
        {
            q = q->lchild;
        }
        return q;
    }
    else //如果当前结点有右孩子就是后继线索
    {
        return p->rchild;
    }
}
//对中序线索二叉树进行中序遍历
void Inorder(ThreadTree T)
{
    ThreadTree t = T;
    //找到第一个被中序遍历的结点
    while (t->ltag == 0 && t->lchild != NULL)
    {
        t = t->lchild;
    }
    while (t != NULL)
    {
        printf("%d", t->data);
        T = NextNode(t);
    }
}

//中序线索二叉树找其前驱
/*
if p->ltag=1  pre=p->lchild
if p->ltag=0  pre=p的左子树最右下的结点

*/
ThreadNode *LastNode(ThreadNode *p)
{
    //找到最右下子节点
    ThreadNode *q = p;
    while (p->rtag == 0)
    {
        q = q->rchild;
    }
    return q;
}
ThreadNode *PreNode(ThreadNode *p)
{
    if (p->ltag == 1)
    {
        return p->lchild;
    }
    else
    {
        return LastNode(p->lchild);
    }
}

/*

对于中序线索二叉树，找前驱和后继都可以
先序线索二叉树只能找后继  除非采用三叉链表，或从头找
后序线索二叉树只能找前驱  除非采用三叉链表，或从头找

*/

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}
#endif